package leetcode.code542.Matrix01;

/**
 *
 * 递归不行啊，极少量可行
 *
 * @author Max
 * @date 2021年8月20日
 * @description
 */
public class Solution54201 extends Matrix01 {

	/**
	 * m == mat.length n == mat[i].length 1 <= m, n <= 104 1 <= m * n <= 104
	 * mat[i][j] is either 0 or 1. mat 中至少有一个 0 
	 */
	@Override
	public int[][] updateMatrix(int[][] mat) {
		for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat[0].length; j++) {
				if (mat[i][j] != 0) {
					min(mat, i, j);
				}
			}
		}
		return mat;
	}

	/**
	 * 某一个点的最小值
	 *
	 * @param mat
	 * @param x
	 * @param y
	 * @return
	 */
	public int min(int[][] mat, int x, int y) {
		if (x >= 0 && y >= 0 && x < mat.length && y < mat[0].length) {
			return Math.min(min(mat, x, y + 1),
					Math.min(min(mat, x, y - 1), Math.min(min(mat, x - 1, y), min(mat, x + 1, y)))) + 1;
		}
		return Integer.MAX_VALUE;
	}

	public static void main(String[] args) {
		Solution54201 so = new Solution54201();
		so.debug1();
		so.debug2();
	}

}
